//============================================================================
// Name        : lab5_1.cpp
// Author      : Binda(蓝达斌)
// Version     :
// Copyright   : Copyright 2011 Binda&Aeolus; All Rights Reserved
// Description :
//根据青蛙换位游戏，使用回溯法编程实现算法解决换位问题。
//在output.txt中给出具体的青蛙跳跃的方案。（给出六只青蛙的位置变化过程）
//============================================================================

#include <iostream>
#include<fstream>
using namespace std;
#define START  1
#define END   7
#define MAX 100
int pos[8]= { 0,-1, -1, -1, 0, 1, 1, 1 };//青蛙的占位从pos[1]开始占位;0表示空位，-1表示起始在左边的只能向右跳的青蛙，1表示起始在右边的只能向左跳的青蛙。
int x[MAX] = { 0 };//空位的移动顺序，起始空位在第4个位置pos[4];x[0]=4;
ofstream out;

const string outfile_name = "output.txt";
//青蛙换位
void swap(int a, int b) {
	int temp = pos[a];
	pos[a] = pos[b];
	pos[b] = temp;
}

//是否换位
bool Solution() {
	return (pos[7] == -1) && (pos[1] == 1) && (pos[2] == 1) && (pos[3] == 1)
			&& (pos[4] == 0) && (pos[5] == -1) && (pos[6] == -1);
}
//输出结果
void outputResult(int t) {

	out<<"The Position Sequence of the Space:"<<endl;
	cout<<"The Position Sequence of the Space:"<<endl;

	for (int i = 0; i < t; i++) {
		cout << x[i] << " ";
		out<<x[i]<<" ";
	}
	cout << endl;
	out<<endl;
	cout<<"Moving Step is:"<<endl;
	out<<"Moving Step is:"<<endl;


	for(int i=1;i<t;i++)
	{

       cout<<":Move "<<x[i]<<" TO "<<x[i-1]<<endl;
       out<<":Move "<<x[i]<<" TO "<<x[i-1]<<endl;
	}
	out << endl;
	out << endl;
	cout << endl;
	cout << endl;

}

void backtrack(int t, int space) {
	if (Solution())
		outputResult(t);
	else
		for (int i = START; i<=END; i++) {

			if (pos[i] == -1)//左边的青蛙
			{
				if ((space - i) == 1 || (space - i) == 2) {
					x[t] = i;
					swap(i, space);
					backtrack(t + 1, i);
					swap(space, i);
				}
			}

			if (pos[i] == 1)//右边的青蛙
			{
				if ((i - space) == 1 || (i - space) == 2) {
					x[t] = i;
					swap(i, space);
					backtrack(t + 1, i);
					swap(space, i);
				}
			}

		}

}

int main() {
	cout << "START" << endl;
    x[0]=4;//首次空位为4
    out.open(outfile_name.c_str());
	backtrack(1, 4);
	out.close();
	cout << "END" << endl;
	return 0;
}

